import sys
sys.setrecursionlimit(300000)
n, m, s = map(int, input().rstrip().split())
graph = [[] for _ in range(n + 1)]
color = [0] * (n + 1)
parent = [0] * (n + 1)
while m > 0:
m -= 1
u, v = map(int, input().rstrip().split())
graph[u].append(v)
def solve():
color[s] = 1
parent[s] = 0
cnt = 2
for i in graph[s]:
assert isinstance(i, int)
color[i] = cnt
parent[i] = s
cnt += 1
def dfs(x):
lst = [x]
while True:
if len(lst) == 0: return None
if len(graph[lst[-1]]) == 0:
lst.pop()
continue
u = graph[lst[-1]].pop()
if color[u] == 0:
color[u] = color[lst[-1]]
parent[u] = lst[-1]
lst.append(u)
elif color[u] == 1 or color[u] == color[lst[-1]]:
pass
else:
return [u, lst[-1]]
for i in graph[s]:
val = dfs(i)
if val and len(val) == 2:
print("Possible")
lst = [val[0]]
while parent[lst[-1]] != 0:
if parent[lst[-1]] < 1 or parent[lst[-1]] > n:
break
lst.append(parent[lst[-1]])
if len(lst) > n: break
print(len(lst))
for i in reversed(lst):
print(i, end=' ')
print()
lst = [val[0], val[1]]
while parent[lst[-1]] != 0:
if parent[lst[-1]] < 1 or parent[lst[-1]] > n:
break
lst.append(parent[lst[-1]])
if len(lst) > n: break
print(len(lst))
for i in reversed(lst):
print(i, end=' ')
print()
return
print("Impossible")
tc = 1
while tc:
solve()
tc -= 1#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <math.h>
#define MAX 200010
#define MM 1000000001
#define ll long long
using namespace std;
int Modul(int x){return x>=0?x: -x;}
vector <int> viz[MAX];
int passou[MAX], w, cam[MAX], end1, end2, t;
bool bfs(int ini){
queue <pair<int,int>> q;
pair<int,int> par;
int no;
for(int i=0;i<viz[ini].size();i++){
q.push(make_pair(viz[ini][i], i+2));
passou[viz[ini][i]]=i+2;
}
passou[ini]=1;
while(!q.empty()){
par=q.front(); q.pop();
//cout << "no=" << par.first << " cor=" << par.second << endl;
no=par.first;
for(int i=0;i<viz[no].size();i++){
if(viz[no][i]!=ini)
if(passou[viz[no][i]]<2){
passou[viz[no][i]]=par.second;
cam[viz[no][i]]=no;
q.push(make_pair(viz[no][i], par.second));
}else if(passou[viz[no][i]]!=par.second){
end1=cam[viz[no][i]]; end2=no; t=viz[no][i];
return true;
}
}
}
return false;
}
int s;
vector <int> caminho(int no){
vector <int> v;
while(cam[no]!=no){
v.push_back(no);
no=cam[no];
}
v.push_back(s);
reverse(v.begin(), v.end());
v.push_back(t);
return v;
}
int main(){
ios_base::sync_with_stdio(0);
int test=1;
//cin >> test;
int n, no, no2, m;
vector <int> c1, c2;
for(int tt=1;tt<=test;tt++){
cin >> n >> m >> s;
for(int i=0;i<=n;i++){
viz[i].clear(); passou[i]=0;
}
cam[s]=s;
for(int i=0;i<m;i++){
cin >> no >> no2;
viz[no].push_back(no2);
}
if(bfs(s)){
cout << "Possible" << endl;
c1=caminho(end1);
c2=caminho(end2);
cout << c1.size() << endl;
for(int i=0;i<c1.size();i++){
cout << c1[i] << " ";
} cout << endl;
cout << c2.size() << endl;
for(int i=0;i<c2.size();i++){
cout << c2[i] << " ";
} cout << endl;
}else{
cout << "Impossible" << endl;
}
}
}
939B - Hamster Farm | 732A - Buy a Shovel |
1220C - Substring Game in the Lesson | 452A - Eevee |
1647B - Madoka and the Elegant Gift | 1408A - Circle Coloring |
766B - Mahmoud and a Triangle | 1618C - Paint the Array |
469A - I Wanna Be the Guy | 1294A - Collecting Coins |
1227A - Math Problem | 349A - Cinema Line |
47A - Triangular numbers | 1516B - AGAGA XOOORRR |
1515A - Phoenix and Gold | 1515B - Phoenix and Puzzle |
155A - I_love_username | 49A - Sleuth |
1541A - Pretty Permutations | 1632C - Strange Test |
673A - Bear and Game | 276A - Lunch Rush |
1205A - Almost Equal | 1020B - Badge |
1353A - Most Unstable Array | 770A - New Password |
1646B - Quality vs Quantity | 80A - Panoramix's Prediction |
1354B - Ternary String | 122B - Lucky Substring |